import java.util.*;

public class Test {
    // 题目1：不同的二叉搜索树 II
    public List<TreeNode> generateTrees(int n) {
        return generateTrees(1, n);
    }

    public List<TreeNode> generateTrees(int start, int end){
        List<TreeNode> list = new LinkedList<>();
        if(start > end){
            list.add(null);
            return list;
        }
        for(int i = start; i <= end; i++){
            List<TreeNode> leftNodes = generateTrees(start, i - 1);
            List<TreeNode> rightNodes = generateTrees(i + 1, end);

            for(TreeNode left : leftNodes){
                for(TreeNode right : rightNodes){
                    TreeNode node = new TreeNode(i);
                    node.left = left;
                    node.right = right;
                    list.add(node);
                }
            }
        }
        return list;
    }

    // 题目2:路径总和
    public boolean hasPathSum(TreeNode root, int target) {
        if(root == null){
            return false;
        }
        if(root.left == null && root.right == null ){
            return target == root.val;
        }
        int tar = target - root.val;
        return hasPathSum(root.left, tar) || hasPathSum(root.right, tar);
    }

    // 题目3：路径总和Ⅱ
    List<List<Integer>> list = new LinkedList<>();
    Deque<Integer> queue = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        searchPathSum(root,  target);
        return list;
    }

    private void searchPathSum(TreeNode root, int target){
        if(root == null){
            return;
        }
        queue.offer(root.val);
        if(root.left == null && root.right == null && root.val == target){
            list.add(new LinkedList(queue));
        }
        int tar = target - root.val;
        searchPathSum(root.left, tar);
        searchPathSum(root.right, tar);
        queue.pollLast();
    }

    // 前缀和模板
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int q = in.nextInt();
            long[] sum = new long[n + 1];
            for(int i = 1; i <= n; i++){
                sum[i] = sum[i - 1] + in.nextInt();
            }
            for(int i = 0; i < q; i++){
                int l = in.nextInt();
                int r = in.nextInt();
                System.out.println(sum[r] - sum[l - 1]);
            }
        }
    }

    //题目4： 路径总和Ⅲ
    // 方法一：遍历
    public int pathSum1(TreeNode root, int target) {
        if(root == null){
            return 0;
        }
        int ret = rootSum(root, target);
        ret += pathSum1(root.left, target);
        ret += pathSum1(root.right, target);
        return ret;
    }

    public int rootSum(TreeNode root, long target){
        int ret = 0;
        if(root == null){
            return 0;
        }
        int val = root.val;
        if(val == target){
            ret++;
        }
        ret += rootSum(root.left, target - val);
        ret += rootSum(root.right, target - val);
        return ret;
    }

    // 题目5： 二叉树的所有路径
    List<String> list1 = new LinkedList<>();
    Deque<Integer> queue1 = new LinkedList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        allTree(root);
        return list1;
    }

    public void allTree(TreeNode root){
        if(root == null){
            return ;
        }
        queue1.offer(root.val);
        if(root.left == null && root.right == null){
            StringBuilder stringBuilder = new StringBuilder();
            for(Integer x : queue1){
                stringBuilder.append(x+"->");
            }
            int end = stringBuilder.length();
            stringBuilder.delete(end - 2, end);
            list1.add(stringBuilder.toString());
        }
        allTree(root.left);
        allTree(root.right);
        queue1.pollLast();
    }

    // 题目六：求根节点到叶节点数字之和
    // 方法一：
    Deque<Integer> queue2 = new LinkedList<>();
    int ret;
    public int sumNumbers(TreeNode root) {
        allPath(root);
        return ret;
    }

    public void allPath(TreeNode root){
        if(root == null){
            return ;
        }
        queue2.offer(root.val);
        if(root.left == null && root.right == null){
            StringBuilder stringBuilder = new StringBuilder();
            for(Integer x : queue2){
                stringBuilder.append(x+"");
            }
            ret += Integer.parseInt(stringBuilder.toString());
        }
        allPath(root.left);
        allPath(root.right);
        queue2.pollLast();
    }

    // 方法二：
    public int sumNumbers1(TreeNode root) {
        return dsf(root, 0);
    }

    public int dsf(TreeNode root, int sum){
        if(root == null){
            return 0;
        }
        sum = sum * 10 + root.val;
        if(root.left == null && root.right == null){
            return sum;
        }else{
            return dsf(root.left, sum) + dsf(root.right, sum);
        }
    }






}
